package real;

import java.util.*;

public class Real {

//    public static void main(String[] args) {
//        Real real = new Real();
//
//        // 测试用例1: 无重叠时间段
//        int[][] test1 = {{1, 3}, {4, 6}, {8, 10}};
//        System.out.println("测试用例1结果: " + real.fixRoad(test1));
//
//        // 测试用例2: 有重叠时间段
//        int[][] test2 = {{1, 4}, {3, 6}, {8, 10}};
//        System.out.println("测试用例2结果: " + real.fixRoad(test2));
//
//        // 测试用例3: 多个重叠时间段
//        int[][] test3 = {{1, 3}, {2, 6}, {8, 10}, {9, 12}};
//        System.out.println("测试用例3结果: " + real.fixRoad(test3));
//
//        // 测试用例4: 完全包含的时间段
//        int[][] test4 = {{1, 10}, {2, 6}, {8, 9}};
//        System.out.println("测试用例4结果: " + real.fixRoad(test4));
//
//        // 测试用例5: 单个时间段
//        int[][] test5 = {{5, 15}};
//        System.out.println("测试用例5结果: " + real.fixRoad(test5));
//
//        // 测试用例6: 相邻时间段
//        int[][] test6 = {{1, 5}, {5, 10}, {10, 15}};
//        System.out.println("测试用例6结果: " + real.fixRoad(test6));
//    }

    //城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为1~H。
    // 同时有交通管理系统会根据不同因素发出拥堵预警:天气预报显示可能有暴雨、大型活动预计车流剧增、早晚高峰时期等。
    // 多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠，比如雨天预警[10,20]和活动预警[15,25]同时存在，
    // 则需要避开整个[10,25]时段进行维修青你帮助多多计算可以进行公路维修的时间共有多少？
    public int fixRoad(int[][] arrays){
        Arrays.sort(arrays, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        ArrayList<int[]> res = new ArrayList<>();
        int[] temp = null;
        for(int i = 0; i < arrays.length; i++){
            if(temp == null){
                temp = arrays[i];
                continue;
            }
            if(temp[1] < arrays[i][0]){
                res.add(temp);
                temp = arrays[i];
            }else {
                temp[1] = Math.max(temp[1],arrays[i][1]);
            }
        }
        res.add(temp);
        int time = 24;
        for (int[] re : res) {
            time -= (re[1] - re[0]);
        }
        return time;
    }

    //在一片神奇的魔法森林中，有n个魔法节点，每个节点都有一个传送门。
    // 第i个节点的传送门会把你传送到a;号节点。
    //多多每次可以选择坐传送门从i节点传送到a;节点，或者选择步行到相邻的节点i-1或i+1节点。
    // 当然多多是个喜欢偷懒的人，所以它能坐传送门就尽量不步行。现在多多从1号节点出发，想知道到达每个节点需要经过的最少步行次数
    //输入描述
    //
    //输入两行，第一行包含一个数字n(1<=n<=100000)，表示有n个节点。接下来一行n个数字，每个数字a;(1<=a;<=n)，表示i节点的传送门可以传送到a节点注意ai可能等于i
    public int[] lowestStep(int[] a, int n){
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            map.put(a[i],i + 1);
        }
        int i = 2;
        while (i <= n){
            if(map.get(i) != null && map.get(i) < i){
                dp[i] = Math.min(dp[i - 1] + 1, dp[map.get(i)]);
            }else {
                dp[i] = dp[i - 1] + 1;
            }
            i++;
        }
        return dp;
    }

    public static void main(String[] args) {
        Real real = new Real();

        // 测试用例1: 简单线性传送
        // 节点1->2->3->4->5，传送门: 1->3, 2->4, 3->5, 4->1, 5->2
        // 传送门数组索引从0开始，即a[0]=3表示节点1传送到节点3
        int[] test1 = {3, 4, 5, 1, 2}; // 节点编号1-5
        int n1 = 5;
        int[] result1 = real.lowestStep(test1, n1);
        System.out.println("测试用例1结果: " + Arrays.toString(result1));
        // 预期: [0, 0, 1, 0, 1, 1] (到达节点1-5的最少步行次数)

        // 测试用例2: 存在自循环
        // 节点1->2->3->4，传送门: 1->1, 2->3, 3->3, 4->2
        int[] test2 = {1, 3, 3, 2};
        int n2 = 4;
        int[] result2 = real.lowestStep(test2, n2);
        System.out.println("测试用例2结果: " + Arrays.toString(result2));
        // 预期: [0, 0, 0, 0, 1]

        // 测试用例3: 线性递增
        // 节点1->2->3->4->5，传送门: 1->2, 2->3, 3->4, 4->5, 5->5
        int[] test3 = {2, 3, 4, 5, 5};
        int n3 = 5;
        int[] result3 = real.lowestStep(test3, n3);
        System.out.println("测试用例3结果: " + Arrays.toString(result3));
        // 预期: [0, 0, 0, 0, 0, 0]

        // 测试用例4: 所有节点都指向第一个节点
        // 节点1->2->3->4，传送门: 1->1, 2->1, 3->1, 4->1
        int[] test4 = {1, 1, 1, 1};
        int n4 = 4;
        int[] result4 = real.lowestStep(test4, n4);
        System.out.println("测试用例4结果: " + Arrays.toString(result4));
        // 预期: [0, 0, 1, 2, 3]

        // 测试用例5: 每个节点都指向下一个节点
        // 节点1->2->3->4->5，传送门: 1->2, 2->3, 3->4, 4->5, 5->1
        int[] test5 = {2, 3, 4, 5, 1};
        int n5 = 5;
        int[] result5 = real.lowestStep(test5, n5);
        System.out.println("测试用例5结果: " + Arrays.toString(result5));
        // 预期: [0, 0, 0, 0, 0, 0]

        // 测试用例6: 单个节点
        // 节点1，传送门: 1->1
        int[] test6 = {1};
        int n6 = 1;
        int[] result6 = real.lowestStep(test6, n6);
        System.out.println("测试用例6结果: " + Arrays.toString(result6));
        // 预期: [0, 0]
    }




    //两个字符串A, B(只包含a、b字符)，构造一个矩阵c，如果a[i] = b[j] = a，则c[i][j] = a，否则c[i][j] = b，
    // 问矩阵C中包含多少个大小为K全为a的子矩阵。

    public int kidMatrix(String a, String b, int k){
        char[][] c = new char[a.length()][b.length()];
        return 1;
    }

    //两个整数序列a、b，可以进行以下操作，任选x、y，如果ai/bi = x，则ai/bi = y，问a=b的最少操作数

}
